package com.exercises;

import java.util.*;

class Exercise218 {

    public static void main(String[] args) {
    }


    public List<List<Integer>> getSkyline(int[][] buildings) {
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> b[1] - a[1]);
        List<Integer> boundaries = new ArrayList<Integer>();
        for (int[] building : buildings) {
            boundaries.add(building[0]);
            boundaries.add(building[1]);
        }
        List<List<Integer>> result = new ArrayList<>();
        Collections.sort(boundaries);
        int length = buildings.length, idx = 0;
        for (int b : boundaries) {
            while (idx < length && buildings[idx][0] <= b) {
                pq.offer(new int[]{buildings[idx][1], buildings[idx][2]});
                idx++;
            }
            while (!pq.isEmpty() && pq.peek()[0] <= b) {
                pq.poll();
            }
            int max = pq.isEmpty() ? 0 : pq.peek()[1];
            if (result.size() == 0 || result.get(result.size() - 1).get(1) != max) {
                result.add(Arrays.asList(b, max));
            }
        }
        return result;


    }
}
